Relational and object-relational database management systems store information in tables in a database. To retrieve data, queries that request data are submitted to a database server, which computes the queries and returns the data requested. Query statements submitted to the database server should conform to the syntactical rules of a particular query language. One popular query language, known as the Structured Query Language (SQL), provides users a variety of ways to specify information to be retrieved.
A query submitted to a database server is evaluated by a query optimizer. Based on the evaluation, the query optimizer generates an execution plan that is optimized for efficient execution. The optimization of a data query typically involves parsing the query to understand its structure and form, and then determining an effective (and, preferably, optimal) manner in which to retrieve or access the requested data.
An execution plan may specify how to access the data, how to format it, and any other operations to be performed. Execution plans may be represented by a graph of interlinked nodes, referred to herein as operators or row sources, that each corresponds to a step of an execution plan, referred to herein as an execution plan operation. The hierarchy of the graphs (i.e., directed tree) represents the order in which the execution plan operations are performed and how data flows between each of the execution plan operations. An execution plan operator generates a set of rows (which may be referred to as a table) as output and execution plan operations include, for example, a table scan, an index scan, sort-merge join, nested-loop join, filter, and full outer join.
SQL supports join operations, which combine the contents of two tables. Join operations fall into two basic categories: an “equijoin” operation in which the selection criteria contains an equality condition, such as requiring a match on one or more join columns common to two tables, as opposed to “non-equijoin” operations which specify conditions other than equality. In either case, the algorithm that performs the join operation must compare each row in one table with each row in every other table designated in the join operation
A band join is a non-equijoin of rows of two tables in which the join condition is a range or band rather than an equality or an open-ended inequality.
A join between tables R and S on attributes R.x and S.y is a band join if the join condition is of the form:R.x−B1<=S.y and R.x+B2>=S.y. 
Band joins can generally be written with the “between” keyword using the syntax:S.y between R.x−B1 and R.x+B2.
The constants B1 and B2 of the band join may be equal and one of them may be zero. Further, one or both of the relational operator may be <or > rather than <=or >=. B1+B2 is referred to as the band length or just band. The band join predicates have the property that a particular value of S.y joins only with the values of R in the interval [S.y−B2, S.y+B1], (S.y−B2, S.y+B1), [S.y−B2, S.y+B1), or (S.y−B2, S.y+B1]. That is, all values matching a particular value of R.x will fall within a band in S.y that has a length B1+B2.
Band joins may be useful in queries that involve real world domains, such as time, position, or price. For example, suppose that a user of the DBMS wants to investigate the correlation between the situation of the stock market and important company events. Two tables, PRICE and NEWS, are involved. Rows of PRICE represent the oscillation of stocks within a day, with attribute PRICE.C representing the time of the measurement in seconds. Rows of NEWS represent financial news articles events, with attribute NEWS.D representing the time in seconds that the article was released.
Suppose the user wants to find all pairs of events occurring at nearly the same time, such that the first event represents a great oscillation of a stock within a day, and the second event represents a news event that mentions the company. Such a query may use a band join. The query may be written in SQL as:
SELECT PRICE. SYMBOL, NEWS.ARTICLE, PRICE.PERCENT CHANGE
FROM PRICE, NEWS
WHERE PRICE.PERCENT CHANGE>10
AND PRICE.C−300<=NEWS.D
AND PRICE.C+300>=NEWS.D
AND NEWS.ARTICLE.CONTAINS (PRICE. SYMBOL)
One of the conditions uses a join operation, in which the difference between attribute, PRICE.C, and attribute, NEWS.D, is between −300 and 300. Rows that meet the join criteria become part of the result table for the query
For band join, the join condition involves a range of values. According to various approaches, the above query is evaluated using either nested-loop or sort-merge join.
Joins on inequality predicates such as those contained in a typical band join are generally quite inefficient. If the query optimizer does not recognize the particular shape of band join predicates, band join queries may result in a very inefficient Cartesian join where many redundant operations are performed.
The approaches described in this section are approaches that could be pursued, but
not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.